﻿// 0728train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits.h>
using namespace std;


/*
 给定一个整数数组 nums 和一个整数目标值 target，
 请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
每种输入只会对应一个答案,数组中同一个元素在答案里不能重复出现。
任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

 */

void GetTargetIndex(vector<int>& nums, int target)
{
    vector<int>oh_vec = nums;
    unordered_map<int, int>oh_map;
    vector<int>result;

    for (int i =0; i < oh_vec.size(); i++)
    {
        int curr_num = oh_vec[i];
        if (oh_map.count(curr_num))
        {
            int prev_index = oh_map[curr_num];
            result.push_back(prev_index);
            result.push_back(i); //curr_index
            break;
        }
        
    	int next_num = target - curr_num;
    	oh_map[next_num] = i; //prev_index
        
    }

    for (auto&num:result)
    {
        cout << num << ' ';
    }


    //GetTargetIndex
}


/*
一个整数数组 nums 和一个整数 k ，
判断数组中是否存在两个 不同的索引 i 和 j ，
满足 nums[i] == nums[j] 且 abs(i - j) <= k 。
如果存在，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [1,2,3,1], k = 3
输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1
输出：true
示例 3：
输入：nums = [1,2,3,1,2,3], k = 2
输出：false

 */
void IsDiffIndex(vector<int>&nums, int k)
{
    vector<int>oh_vec = nums;

    unordered_map<int, int>oh_map;

    int diff = k;

    bool result = false;

    for (int i=0; i<oh_vec.size(); i++)
    {
        int curr_num = oh_vec[i];
	    if (oh_map.count(curr_num))
	    {
            int prev_index = oh_map[curr_num];
            int curr_index = i;

            //cout << "prev: " << prev_index << "_curr: " << curr_index << endl;
            //cout << "abs: " << abs(prev_index - curr_index) << endl;

            if (abs(prev_index-curr_index)<=diff)
            {
                result = true;
                break;
            }

            //相等，不满足diff，更新prev_index
             oh_map[curr_num] = i;
            

	    }
    	else
    	{
            oh_map[curr_num] = i;
    	}
    }

    cout << result;

    //IsDiffIndex
    //------
}

/*
 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。
不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

 示例 1:
输入：s = "egg", t = "add"
输出：true
示例 2：
输入：s = "foo", t = "bar"
输出：false
示例 3：
输入：s = "paper", t = "title"
输出：true
  12134
 */

vector<int>GetCodeVec(string oh_str_1)
{
    unordered_map<int, int>oh_map;

    int code = 1;
    vector<int>code_vec_1;
    for (auto& oh_char : oh_str_1)
    {
        if (oh_map.count(oh_char))
        {
            int curr_code = oh_map[oh_char];
            code_vec_1.push_back(curr_code);
        }
        else
        {
            code_vec_1.push_back(code);
            //存一个新的，更新一次code
            oh_map[oh_char] = code;
            code += 1;
        }
    }
    return code_vec_1;
}

bool isSameStruct(string s, string t)
{
    string oh_str_1 = s;
    string oh_str_2 = t;

    vector<int> code_vec_1 = GetCodeVec(oh_str_1);
    vector<int> code_vec_2 = GetCodeVec(oh_str_2);
    //for (auto&num: code_vec_2)
    //{
    //    cout << num << ' ';
    //}
    if (code_vec_1.size()!=code_vec_2.size())
    {
        return false;
    }

    bool result = true;
    
    for (int i=0; i<code_vec_1.size();i++)
    {
        int curr_num = code_vec_1[i];
        int reflect_num = code_vec_2[i];
	    if (curr_num!= reflect_num)
	    {
            result = false;
            break;
	    }
    }
    return result;
    
    //isSameStruct
}


/*
 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。 
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
 */
unordered_map<char,int>GetCharMap(string oh_str)
{
    unordered_map<char, int>char_map;
    for (auto &oh_char:oh_str)
    {
	    if (char_map.count(oh_char))
	    {
            char_map[oh_char] += 1;
	    }
        else
        {
            char_map[oh_char] = 1;
        }
    }
    return char_map;
    //GetCharMap
}

bool IsReflect(string oh_str, unordered_map<char, int>&origin_map)
{
    bool result = true;
    unordered_map<char, int>oh_map;
    for (auto &map_item:origin_map)
    {
        oh_map[map_item.first] = map_item.second;
    }

    for (auto&oh_char:oh_str)
    {
	    if (!oh_map.count(oh_char))
	    {
            result = false;
            break;
	    }
        if (oh_map[oh_char]==0)
        {
            result = false;
            break;
        }
        oh_map[oh_char] -= 1;
    }

    return result;
    //IsReflect
}

vector<vector<string>>GetSameStructVec(vector<string>&strs)
{
    //双重遍历，取出0，从1位置开始遍历，
    //map存已经遍历的

    vector<vector<string>>result_vec;
    unordered_map<string, int>string_map;

    if (strs.size()==1)
    {
        result_vec.push_back(strs);
        return result_vec;
    }

    vector<string>str_vec = strs;

    for (int i_1=0; i_1< str_vec.size(); i_1++)
    {
        string curr_str = str_vec[i_1];
        unordered_map<char, int>char_map = GetCharMap(curr_str);
        vector<string>reflect_vec = { curr_str };

        //for (auto&map_item:char_map)
        //{
        //    cout << map_item.first << ' ';
        //}
        //cout << '\n';

        //cout << IsReflect(str_vec[1], char_map);
        //break;
        //已经匹配过了，不再新增vector
        //cout << curr_str << " : " << str_set.count(curr_str) << endl;

        if (string_map.count(curr_str)) continue;
        string_map[curr_str] = i_1;


        //正确路径
        for (int j_2=i_1+1; j_2< str_vec.size();j_2++)
        {
            string reflect_str = str_vec[j_2];
            
	        if (string_map.count(reflect_str))
	        {
                //已经匹配过了
                continue;
	        }

            //查询是否匹配
            if (IsReflect(reflect_str, char_map))
            {
                reflect_vec.push_back(reflect_str);
                string_map[reflect_str] = j_2;
            }

            //for j_2-------
        }
        
        result_vec.push_back(reflect_vec);

    }

    //cout << result_vec.size();
    return result_vec;
    //GetSameStructVec
}


/*
 放弃，尝试自己解决失败
 失败原因：map里存的是string，发现行不通，因为string是有可能相同的
 相同的string一进去, oh_map.count()==1直接就不处理了
 */

/*
 尝试练习老师给的方法
 指定一个0-26的数组，按照字母存进去
 把数组抽成一个键值string

 for，map.count(string)==0 map[string] = []

 最后，扫一遍map
 */

vector<vector<string>>GetSameStructVec02(vector<string>& strs)
{
    unordered_map<string, vector<string>>oh_map;

    vector<string>oh_vec = strs;

    for (int i = 0; i < oh_vec.size(); i++)
    {
        vector<int>char_vec(26);

        string curr_string = oh_vec[i];
        for (auto& oh_char : curr_string)
        {
            int char_num = oh_char - 'a';
            char_vec[char_num] += 1;
        }

        string key;
        for (int i = 0; i < char_vec.size(); i++)
        {
            key += to_string(i);
            key += to_string(char_vec[i]);
            key += '#';
        }

        oh_map[key].push_back(curr_string);


        //for------
    }

    vector<vector<string>>result_vec;

    for (auto& map_item : oh_map)
    {
        result_vec.push_back(map_item.second);
    }

    //cout << result_vec.size();
    return result_vec;

    //GetSameStructVec02
}


int main()
{

	{
		//输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
        //输出 : [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

        //vector<string>strs = { "eat", "tea", "tan", "ate", "nat", "bat" };

        //输入["",""]  输出 [["",""]]
        vector<string>strs = { "", "" };

        GetSameStructVec02(strs);

        return 0;
	}

	{
        //s = "paper", t = "title" true
        //s = "foo", t = "bar" false
        //s = "egg", t = "add" true
        string s = "egg", t = "add";
        cout << isSameStruct(s, t);

        return 0;
	}

	{
        //nums = [1,2,3,1], k = 3 true
        //nums = [1,0,1,1], k = 1 true
        //nums = [1,2,3,1,2,3], k = 2 false

        vector<int>nums = { 1,2,3,1,2,3 };
        int k = 2;
        IsDiffIndex(nums, k);

        return 0;
	}


    //nums = [2,7,11,15], target = 9 [0,1]
    //nums = [3,2,4], target = 6 [1,2]
    //nums = [3,3], target = 6 [0,1]
    vector<int>oh_vec = { 3,3 };
    int target = 6;
    GetTargetIndex(oh_vec, target);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
